//
// Created by ASUS on 2023/10/13.
//

#include <bits/stdc++.h>
using namespace std;

//单源最短路，从start到其他各点最短路，无负数，邻接表
int dijkstra(int n,vector<vector<int>>& edges,int start,int end){
	vector<vector<pair<int, int>>> g(n);
	vector<int> pre(n);
	for(int i=0;i<edges.size();i++){
		auto &e=edges[i];
		g[e[0]].emplace_back(e[1],e[2]);
		g[e[1]].emplace_back(e[0],e[2]);
	}

	vector<int> dis(n+1,INT_MAX/2);//起点到每个点的最短距离
	dis[start]=0;
	priority_queue<pair<int,int>,vector<pair<int,int>>,greater<>> pq;
	pq.emplace(0,start);
	while (!pq.empty()){
		auto[dx,x]=pq.top();
		pq.pop();
		if(dis[x]<dx) continue;
		for(auto&[y,d]:g[x]){
			int new_dis=d+dx;
			if(new_dis<dis[y]){
				dis[y]=new_dis;
				pre[y]=x;
				pq.emplace(new_dis,y);
			}
		}
	}
	//逆序输出方案
	vector<int> path;
	int i=end;
	path.push_back(i);
	while(i!=start){
		i=pre[i];
		path.push_back(i);
	}
	return dis[end];
}

//单源最短路，从start到其他各点最短路，无负数，邻接表
int dijkstra1(int n,vector<vector<int>>& edges,int start,int end){
	vector<vector<pair<int, int>>> g(n);
	vector<int> pre(n);
	for(int i=0;i<edges.size();i++){
		auto &e=edges[i];
		g[e[0]].emplace_back(e[1],e[2]);
		g[e[1]].emplace_back(e[0],e[2]);
	}

	vector<int> dis(n+1,INT_MAX/2);//起点到每个点的最短距离
	dis[start]=0;
	priority_queue<pair<int,int>> pq;
	pq.emplace(0,start);
	while (!pq.empty()){
		auto[dx,x]=pq.top();
		dx=-dx;
		pq.pop();
		if(dis[x]<dx) continue;
		for(auto&[y,d]:g[x]){
			int new_dis=d+dx;
			if(new_dis<dis[y]){
				dis[y]=new_dis;
				pre[y]=x;
				pq.emplace(-new_dis,y);
			}
		}
	}
	//逆序输出方案
	vector<int> path;
	int i=end;
	path.push_back(i);
	while(i!=start){
		i=pre[i];
		path.push_back(i);
	}
	return dis[end];
}



//邻接矩阵，两两之间最短路  数据范围n<200,允许有负,但不能有负环
void floyd(int n,vector<vector<int>>& edges){
	vector<vector<int>> dis(n,vector<int>(n,INT_MAX/2));
	for(int i=0;i<n;i++) dis[i][i]=0;
	for(auto&e:edges){
		dis[e[0]][e[1]]=min(dis[e[0]][e[1]],e[2]);
		dis[e[1]][e[0]]=min(dis[e[1]][e[0]],e[2]);
	}
	for (int k = 0; k <n; k++) {
		for (int i = 0; i <n; i++) {
			if (dis[i][k] == INT_MAX / 2) { // 加上这句话，巨大优化！
				continue;
			}
			for (int j = 0; j < n; j++) {
				dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
			}
		}
	}
}

bool bellman_ford(int n,vector<vector<int>>&edges,vector<int>& weights,int start){
	vector<vector<pair<int, int>>> g(n+1);//邻接表,结点从1开始，大小n+1
	for(int i=0;i<edges.size();i++){
		auto &e=edges[i];
		g[e[0]].emplace_back(e[1],weights[i]);//有向图只有一个
	}
	vector<int> dis(n+1,INT_MAX/2);//起点到每个点的最短距离
	dis[start]=0;
	bool flag;
	for(int i=1;i<=n;i++){
		flag = false;
		for (int u = 1; u <= n; u++) {
			if (dis[u] == INT_MAX/2) continue;
			// 无穷大与常数加减仍然为无穷大
			// 因此最短路长度为 inf 的点引出的边不可能发生松弛操作
			for (auto&[v,w]: g[u]) {
				if (dis[v] > dis[u] + w) {
					dis[v] = dis[u] + w;
					flag = true;
				}
			}
		}
		// 没有可以松弛的边时就停止算法
		if (!flag) break;
	}
	return flag;
}

